﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text
{
    //给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
    //说明：每次只能向下或者向右移动一步。[[1,3,1],[1,5,1],[4,2,1]]
    /// <summary>
    /// 64. 最小路径和
    /// </summary>
    public class _64
    {
        public int minPathSum(int[][] grid)
        {
            for (int i = 0; i < grid.Length; i++)//y的长度
            {
                for (int j = 0; j < grid[0].Length; j++)//x的长度
                {
                    if (i == 0 && j == 0) continue;
                    else if (i == 0) grid[i][j] = grid[i][j - 1] + grid[i][j];
                    else if (j == 0) grid[i][j] = grid[i - 1][j] + grid[i][j];
                    else grid[i][j] = Math.Min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
                }
            }
            return grid[grid.Length - 1][grid[0].Length - 1];
        }
        public int OtherMinPathSum(int[][] grid)
        {
            int row = grid.Length;
            int col = grid[0].Length;
            int[,] dp = new int[row,col];
            dp[0, 0]= grid[0][0];
            for (int i = 1; i < row; i++)//吧二维col边上的赋值
                dp[i,0] = dp[i - 1,0] + grid[i][0];
            for (int j = 1; j < col; j++)//吧二维col边上的赋值
                dp[0,j] = dp[0,j-1] + grid[0][j];
            for (int i = 1; i < row; i++)
            {
                for (int j = 1; j < col; j++)
                {
                    dp[i,j] = Math.Min(dp[i-1,j],dp[i,j-1])+grid[i][j];
                }
            }
            return dp[row - 1,col - 1];
        }
    }
}
